﻿using System;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch sw = new Stopwatch();
        static Random rand;
        private static long _before;
        static void Main(string[] args)
        {

            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
            rand = new Random();
           // Console.WriteLine(args.Length);
         //   int[] myArray=new int[args.Length-1];
            if (args.Length < 2)
            {
                Console.WriteLine("Bitte gib als erstes Argument die Methode der Medianberechnung an(qs,hs, oder wr) sowie danach eine Textdatei");
            }
            else
            {

                //for (int i = 1; i < args.Length; i++)
                //{
                //    myArray[i-1] = Convert.ToInt32(args[i]);
                // //   Console.WriteLine(args[i]);
                //}
                string fileContent = System.IO.File.ReadAllText(args[1]);
              string[] integerStrings = fileContent.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
               int[] myArray = new int[integerStrings.Length];
               for (int n = 0; n < integerStrings.Length; n++)
               {
                   myArray[n] = int.Parse(integerStrings[n]);
               }
                sw.Start();
                _before = Process.GetCurrentProcess().WorkingSet64;
                switch (args[0])
                {
                    case "qs": quicksort(myArray); break;
                    case "hs": HeapSortMedianSearch.medianHeapSortSelect(myArray); break;
                    case "wr": writh(myArray);  break;
                    default: break;

                }
                sw.Stop();
                var memoryInKb = (Process.GetCurrentProcess().WorkingSet64 - _before) / 1024.0;
                Console.WriteLine("Memory: {1}kb{0}", Environment.NewLine, memoryInKb);
                string ExecutionTimeTaken = string.Format("Minutes :{0}\nSeconds :{1}\n Mili seconds :{2}", sw.Elapsed.Minutes, sw.Elapsed.Seconds, sw.Elapsed.TotalMilliseconds);
                Console.WriteLine(ExecutionTimeTaken);
                Console.Read();
            }
        }
        private static void writh(int[] array)
        {
            int medloc = -1;
            int medloc2 = -1;
            double res = -1;
            medloc = ((array.Length - 1) / 2);
            int loc = -1;
            if (array.Length % 2 == 0)
            {
                medloc2 = medloc + 1;
               // medloc = medloc2 - 1;
                int med = getWrithSort(array, medloc);
                int med1 = getWrithSort(array, medloc2);
                res = ((double)med + (double)med1) / 2;
                //if(res!=3.5)
                Console.WriteLine("Der Median nach Writh ist: " + res);

            }
            else
            {

                loc = getWrithSort(array, medloc);
                int myNumb = loc;
               // myNumb = 50001;
                Console.WriteLine("Der Median nach Writh ist: " + myNumb);

            }
            

        }

        private static int getWrithSort(int[] a, int k)
        {
            int x;
            int i,j = -1;
            int m = a.Length-1;
            for (int l = 0; l <= m; l++)
            {
                x = a[k];
                i = l;
                j = m;
                do
                {
                    while (a[i] < x) i++;
                    while (x < a[j]) j--;
                    if (i <= j)
                    {
                        int temp = a[i];
                        a[i] = a[j];
                       a[j]=temp;
                        i++; j--;
                    }
                } while (i <= j);
                if (j < k) l = i;
                if (k < i) m = j;
            }
            return a[k];
        
        }

           private static void quicksort(int[] array)
        {
        
    

            //for (int katsching = 0; katsching < 100000; katsching++)
            //{
                int medloc = -1;
                int medloc2 = -1;
                double res = -1;
                medloc = (array.Length + 1) / 2;
                int loc = -1;
                if (array.Length % 2 == 0)
                {
                    medloc2 = (array.Length) / 2;
                    medloc = medloc2 + 1;
                    int med = array[random_selection(array, 0, array.Length - 1, medloc)];
                   int med1 = array[random_selection(array, 0, array.Length - 1, medloc2)];
                    res = ((double)med + (double)med1) / 2;
                    //if(res!=3.5)
                    Console.WriteLine("Der Median nach Quicksort ist: " + res);

                }
                else
                {

                    loc = random_selection(array, 0, array.Length - 1, medloc);
                    Console.WriteLine("Der Median nach Quicksort ist: " + array[loc]);

                }

                // int loc = random_selection(array, 0, array.Length, 5);
            //}

        }


        private static int random_partition(int[] arr, int start, int end)
        {
            int pivotIdx =-1;
            //if (start + 1 <= end - 1)
            //{
            //    pivotIdx = rand.Next(start + 1, end - 1); 
            //}
            //else 
            pivotIdx = rand.Next(start, end);

            int pivot = arr[pivotIdx];
            int tem = arr[pivotIdx];
            arr[pivotIdx] = arr[end];
            arr[end] = tem;
            pivotIdx = end;

            int i = start - 1;



            for (int j = start; j <= end - 1; j++)
            {

                if (arr[j] <= pivot)
                {

                    i = i + 1;
                    tem = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tem;

                }

            }

            tem = arr[i + 1];
            arr[i + 1] = arr[pivotIdx];
            arr[pivotIdx] = tem;
            return i + 1;

        }



      private static int random_selection(int[] array, int start, int end, int i)
      {

            if (start == end)

                return start;



            if (i == 0) return -1;



            if (start < end)
            {



                int mid = random_partition(array, start, end);

                int j = mid - start + 1;

                if (j == i)

                    return mid;

                else if (i < j)

                    return random_selection(array, start, mid - 1, i);

                else

                    return random_selection(array, mid + 1, end, i - j);

            }
            else return -1;



        }
    }
}
